package com.klun.project.common.constans.utils;

import java.util.Comparator;

public class SortUtils {

	/**
	 * 快速排序
	 */
	public static <T> void quickSort(T[] in, Comparator<? super T> comparator) {
		quickSort(in, comparator, 0, in.length - 1);
	}

	public static <T> void quickSort(T[] in, Comparator<? super T> comparator, int start, int end) {
		if (start >= end) {
			return;
		}
		int index = swap(in, comparator, start, end);
		quickSort(in, comparator, start, index - 1);
		quickSort(in, comparator, index + 1, end);
	}

	public static <T> int swap(T[] in, Comparator<? super T> comparator, int start, int end) {
		T t = in[start];
		int left = start;
		int right = end;
		while (left < right) {
			while (left < right && comparator.compare(t, in[left]) >= 0) {
				++left;
			}
			while (left < right && comparator.compare(t, in[right]) < 0) {
				--right;
			}
			if (left < right) {
				T tmp = in[left];
				in[left] = in[right];
				in[right] = tmp;
			}
		}
		in[start] = in[right];
		in[right] = t;
		return right;
	}

	/**
	 * 快速排序
	 */
	public static void quickSort(int[] in) {
		quickSort(in, 0, in.length - 1);
	}

	public static void quickSort(int[] in, int left, int right) {
		if (left >= right) {
			return;
		}
		// 第一个 left参数 交换后的位置
		int pivotIndex = doublePointerSwap(in, left, right);
		quickSort(in, left, pivotIndex - 1);
		quickSort(in, pivotIndex + 1, right);
	}

	// 双指针交换
	public static int doublePointerSwap(int[] in, int left, int right) {
		int pivot = in[left];
		int l = left;
		int r = right;
		while (l < r) {
			while (l < r && in[r] > pivot) {
				r--;
			}
			while (l < r && in[l] <= pivot) {
				l++;
			}
			if (l < r) {
				int temp = in[l];
				in[l] = in[r];
				in[r] = temp;
			}
		}
		in[left] = in[r];
		in[r] = pivot;
		return right;
	}

	public static void main(String[] args) {

	}

}
